package com.dy.分类.链表.删除链表的倒数第N个节点;
/*
删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？
 */


import com.dy.分类.链表.ListNode;

import java.util.*;


public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> list = new ArrayList<ListNode>();
        while(head.next!=null){
            list.add(head);
            head = head.next;
        }
        list.add(head);
        if(list.size()==1){
            return null;
        }
        if(list.size()==n){
            return list.get(0).next;
        }
        list.get(list.size()-n-1).next= list.get(list.size()-n).next;

        return list.get(0);
    }
    /*
    第二种方法，先遍历n个
     */
    public ListNode removeNthFromEnd2(ListNode head,int n){
        ListNode p = head;
        ListNode q= head;
        for(int i =0;i<n;i++){
            p=p.next;
        }
        //正顺序遍历n个，如果遇到结尾，说明一共长为n，倒序是head
        if(p ==null){
            return head.next;
        }
        while(p.next!=null){
            p=p.next;
            q=q.next;
        }
        q.next =q.next.next;
        return head;
    }
}
